package com.lw.leetcode.sort.c;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 632. 最小区间
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/26 16:17
 */
public class SmallestRange {

    public static void main(String[] args) {
        SmallestRange test = new SmallestRange();
        List<List<Integer>> nums = new ArrayList<>();

        // [20,24]
//        nums.add(Arrays.asList(4,10,15,24,26));
//        nums.add(Arrays.asList(0,9,12,20));
//        nums.add(Arrays.asList(5,18,22,30));

        // [1,1]
        nums.add(Arrays.asList(1, 2, 3));
        nums.add(Arrays.asList(1, 2, 3));
        nums.add(Arrays.asList(1, 2, 3));

        int[] ints = test.smallestRange(nums);
        System.out.println(Arrays.toString(ints));
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        int size = nums.size();
        int a = -1;
        int b = -1;
        PriorityQueue<Long> queue = new PriorityQueue<>();
        int max = Integer.MIN_VALUE;
        int item = Integer.MAX_VALUE;
        for (int i = 0; i < size; i++) {
            int v = nums.get(i).get(0);
            queue.add((((long) v) << 32) + (i << 16));
            max = Math.max(max, v);
        }
        while (!queue.isEmpty()) {
            long poll = queue.poll();
            int v = (int) (poll >> 32);
            int x = ((int) poll) >> 16;
            int y = (int) (poll & 0XFFFF);
            if (item > max - v) {
                item = max - v;
                a = v;
                b = max;
            }
            List<Integer> list = nums.get(x);
            y++;
            if (y == list.size()) {
                break;
            }
            int c = nums.get(x).get(y);
            max = Math.max(max, c);
            queue.add((((long) c) << 32) + (x << 16) + y);
        }
        return new int[]{a, b};
    }

}
